package com.yxp.offer;

import com.yxp.middle.Problem1008;
import com.yxp.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : yang.xp
 * @date : 2021/8/18 15:34
 * @description : 剑指 Offer 32 - III. 从上到下打印二叉树 III
 */
public class Problem32_3 {

    public static void main(String[] args) {
        int[] numbers = new int[]{8, 5, 1, 7, 10, 12};
        Problem1008 problem1008 = new Problem1008();
        TreeNode treeNode = problem1008.bstFromPreorder(numbers);
        Problem32_3 problem32_3 = new Problem32_3();
        System.out.println(problem32_3.levelOrder(treeNode));
    }

    public List<List<Integer>> levelOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> resultList = new ArrayList<>();
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        treeNodeQueue.add(treeNode);
        int flow = 0;
        while (!treeNodeQueue.isEmpty()) {
            List<Integer> integers = addFlow(treeNodeQueue, flow++);
            resultList.add(integers);
        }
        return resultList;
    }

    public List<Integer> addFlow(Queue<TreeNode> treeNodeQueue, int flow) {
        LinkedList<Integer> tempList = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        while (!treeNodeQueue.isEmpty()) {
            TreeNode poll = treeNodeQueue.poll();
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
            if (flow % 2 != 0) {
                tempList.addFirst(poll.val);
            } else {
                tempList.addLast(poll.val);
            }
        }
        treeNodeQueue.addAll(queue);
        return tempList;
    }
}
